Digital information can be represented as a series of data objects to facilitate processing and storing the digital information. For example, a digital audio or video file can be represented as a series of data objects that contain digital audio or video samples. More generally, a data object is an aggregation of digital information that is related along spatial, temporal, conceptual, or any other lines of significance.
When a series of data objects represents digital information, processing the series is simplified if the data objects are equal size. For example, suppose a video sequence of uncompressed, equal-size images is stored in a data structure. Using an ordinal number of an image in the video sequence, and knowing the size of images in the sequence, a particular image in the video sequence can be accessed as an offset from the beginning of the data structure.
Although access to equal-size data objects in a series is relatively straightforward, in some applications, use of equal-size data objects leads to inefficient storage and transmission. For example, when a video sequence is compressed, video frames may compress to varying sizes. By representing such digital information in variable-size data objects [“VSDOs”], storage and transmission is made more efficient.
Accessing a particular VSDO within a series of VSDOs is relatively complicated, however. Due to the variable sizes of the data objects preceding the VSDO to be accessed, the starting position of the VSDO to be accessed cannot be known based upon an ordinal series number. Thus, to access a VSDO, the VSDOs that precede the VSDO to be accessed must be traversed.
FIG. 3 shows a prior art data stream 100 for a compressed image. The data stream 100 starts with a header 110. Blocks 120 of data, corresponding to entropy-coded, quantized transform coefficients for blocks of the image, follow the header 110. The blocks 120 have variable length. Each block indicates its end with an end of block code 130. After an end of block code 130, the following block 120 begins. The data stream 100 ends with an end of stream code 140.
Consider, for example, a decompression and display technique in which data in every block 120 of data stream 100 is accessed and decoded in order to display the compressed image in data stream 100. Starting from the beginning of the data stream 100, blocks 120 are accessed and decoded in a linear manner until the end of stream code 140 is reached. Although linear retrieval of blocks is time consuming, every block that is retrieved is also used. Similarly, if a video sequence is encoded into a data stream such as data stream 100, each block of data is retrieved and used to display the video sequence.
In contrast, consider a light field rendering operation, which has different characteristics than a video display operation. In a light field rendering operation, light field samples dispersed throughout a light field are retrieved and processed to estimate a view from some arbitrary point in space.
A light field models the light characteristics of an object or static scene, for example, by capturing light intensity and color values along a surface around a static scene. To map a light field to a computational framework requires a discrete representation. FIGS. 1 and 2 depict a discretized light field 10. Light field 10 includes a set of spatially-related light field images of an object 20. FIG. 1 shows expanded views of light field images 12 and 14. A light field image comprises a two-dimensional arrangement (s,t) of data values such as values from a color space. Light rays from the object 20 that pass through a light field image (s,t) also pass through a focal point 32 in the (u,v) plane. A (s,t,u,v) grid point is indexed with (i,j,p,q). Capture and generation of light fields, different parameterizations of light fields, and light field image rendering, as well as other aspects of light fields, are described in Gortler et al., “The Lumigraph,” Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 43–54 [“the Gortler reference”] and Levoy et al., “Light Field Rendering,” Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 31–42 [“the Levoy reference”].
Storage and transmission of light fields present difficulties due to the amount of digital information in a typical light field. An illustrative light field consists of 16×16 focal points in the focal plane (u,v). If each light field image has a resolution of 256×256 and stores 24-bit RGB values, the total amount of storage is: 16×16×256×256×3 bytes=48 Mbytes. Compression of light field information can reduce the representation of the light field image information, usually at some cost to the quality of the information and the speed of accessing the information. Compression of light field information typically results in VSDOs.
In addition to the considerable storage and transmission requirements for a light field, manipulation of light field images presents considerable memory and processing requirements. Light field rendering is the process of creating a view of an object or static scene based upon a light field, e.g., by interpolating from known light field image values. During light field rendering, parts of selected light field images are retrieved to construct a view from a novel perspective. Depending on the perspective of the novel view being rendered, different light field images are retrieved. Because rendering typically uses different parts of different light field images according to a complex pattern of access, random access to parts of light field images facilitates rendering. Unfortunately, loading multiple light field images into random access memory (to facilitate random access to dispersed light field samples) consumes large amounts of memory given the size of a typical light field image. Moreover, even after light field images are loaded into memory, light field operations are computationally complex, especially when decompression of the light field information is required.
These high memory and processing requirements hinder real time rendering, especially for serialized rendering operations. To return to FIG. 3, suppose that during a light field rendering operation only the light field information in Block n 126 needs to be accessed. The starting point of block n 126 is not known in advance. The sizes of the blocks 120 preceding block n 126 are not known in advance. Even though only information in block n 126 is needed, it is necessary to start retrieving blocks in a linear manner from the beginning of the data stream 100. This linear, sequential retrieval wastes resources because many blocks that are retrieved are not used in the rendering operation. This inefficiency is exacerbated when numerous non-sequential, dispersed light field samples must be retrieved. Furthermore, retrieval of block n 126 can be disrupted by corruption of the data preceding block n 126 in the data stream 100.